package edu.gdkm.demo3;
//斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...
//实现程序，计算出数列第50项的数组
public class Test4 {
    public static long fibonacci(int n){
        long x,y,z;
        x=1;
        y=1;
        z=0;
        if(n==1||n==2){
            return 1;
        }else{
            for(int i=3;i<=n;i++){
                z=x+y;
                x=y;
                y=z;
            }
            return z;
        }

    }
    public static long fibonacci_2(int n){
        if(n==1||n==2){
            return 1;
        }else {
            long fibos[] = new long[n + 1];
            fibos[0] = 0;
            fibos[1] = 1;
            fibos[2] = 1;
            for (int i = 3; i <= n; i++) {
                fibos[i] = fibos[i - 1] + fibos[i - 2];
            }
            return fibos[n];
        }
    }
    public static long fibonacci_3(int n){
        if(n==1||n==2){
            return 1;
        }else {
            return fibonacci_3(n-1)+fibonacci_3(n-2);
        }
    }
    public static void main(String[] args) {
        for(int i=1;i<50;i++){
            System.out.print(fibonacci(i)+" ");
        }
        System.out.println();
        for(int i=1;i<50;i++){
            System.out.print(fibonacci_2(i)+" ");
        }
        System.out.println();
        for(int i=1;i<50;i++){
            System.out.print(fibonacci_3(i)+" ");
        }
    }
}
